package org.lex.collection;

import java.util.Collection;

public class MaxHeap<E> extends Heap<E> {
	public MaxHeap() {
		super();
	}

	public MaxHeap(Collection<E> c) {
		super(c);
	}

	@Override
	protected void buildHeap() {
		int firstLeafIndex = this.getFirstLeaf();
		for (int i = firstLeafIndex - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}

	@Override
	protected void heapifyDown(int index) {
		int length = this.size();
		int leftChildIndex = this.getLeftChild(index);
		int rightChildIndex = this.getRightChild(index);

		E currentValue = this.get(index);
		int largestElementIndex = index;
		if (leftChildIndex < length && this.compare(this.get(leftChildIndex), currentValue) > 0) {
			largestElementIndex = leftChildIndex;
		}

		if (rightChildIndex < length && this.compare(this.get(rightChildIndex), this.get(largestElementIndex)) > 0) {
			largestElementIndex = rightChildIndex;
		}
		if (index != largestElementIndex) {
			this.swap(index, largestElementIndex);
			this.heapifyDown(largestElementIndex);
		}
	}

	@Override
	protected void heapifyUp(int index) {
		int parentIndex = this.getParent(index);
		if (parentIndex < 0) {
			return;
		}
		if (this.compare(this.get(parentIndex), this.get(index)) < 0) {
			this.swap(parentIndex, index);
			this.heapifyUp(parentIndex);
		}
	}

	@Override
	protected boolean isHeap() {
		boolean isHeap = true;
		int length = this.size();
		for (int i = 0; i < this.getFirstLeaf(); i++) {
			int parent = i;
			E parentValue = this.get(parent);
			int left = this.getLeftChild(parent);
			if (left < length && this.compare(this.get(left), parentValue) > 0) {
				isHeap = false;
				break;
			}

			int right = this.getRightChild(parent);
			if (right < length && this.compare(this.get(right), parentValue) > 0) {
				isHeap = false;
				break;
			}
		}
		return isHeap;
	}

	// ========== java.util.Collection ==========
	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}
}
